今天我們來看一題延伸題，在LeetCode上面難度為Hard

題目是這樣的:

有一種產品，名為俄羅斯套娃信封．一組產品裡面有數個不同大小的信封，並且可以層層收納．大概就像是下圖這樣，三個信封可以收納成一個．

現在，給一組陣列，陣列中的每一個元素都代表著一個信封的長與寬．求使用這組信封，最多可以組出幾層的套娃．長寬不能交換順序．

例如:給信封陣列 envelops = [[5,4],[6,4],[6,7],[2,3]]，最後會返回3 表示最多可以套三層 ，分別是[2,3]⇒[5,4]⇒[6,7]

這題其實是昨天最長遞增子序列的延伸題，很顯然，每次合法的嵌套就是大的套小的，相當於找一個最長遞增的子序列，其長度就是最多能嵌套的信封個數．

但是一般的LIS演算法只能在一維陣列中尋找，而信封是由[w,h]的二維陣列表示，要如何去運用LIS演算法呢？

一個最簡單的想法，我們把信封的長與寬相乘，得到面積，這樣就獲得了一個一維陣列，這樣就能使用LIS了．

但是實際上不行，比如1 * 10 的面積大於 3 * 3的面積，但是實際上 1 * 10裝不進 3 * 3的信封

解法思路

先來一個測資，我們在慢慢推倒到通則

假設 envelops = [[2,3],[5,2],[6,4],[5,4],[1,8],[6,7]]

我們先保證一邊是可行通過的，所以先照一個維度是合法的，就用前面的寬度w吧，排列起來像是這樣

左邊這排寬度w照升冪排好
[1,8]
[2,3]
[5,2]
[5,4]
[6,4]
[6,7]

然後高度h的部分，就像昨天分牌堆一樣，將其使用降冪排序

右邊這排高度h照降冪排好
[1,8]
[2,3]
[5,2]//這邊跟下面那行交換了
[5,4]
[6,4]//這邊跟下面那行交換了
[6,7]

然後使用h尋找最長遞增子序列 得到 3⇒4⇒7的最長子序列，而由於寬度我們也進行過排序，因此不會發生塞不進去的情況．整體信封嵌套的情況就是[2,3]⇒[5,4]⇒[6,7]

這個解法的重點就在對於相同寬度的w陣列，要對其高度h進行降冪排序．

因為兩個w相同的信封不能互相包含，w相同時將h進行降冪排序，則在這個降冪的陣列中，最多只會有一個選入遞增子序列，確保最終的信封序列不會出現w相同的情況

當然也能反過來解，先固定高度h再反過來排序寬度w，最後使用w做LIS得出結果．

有了思路我們來實作吧

fun maxEnvelops(envelops: Array<IntArray>): Int {
    val n = envelops.size
    envelops.sortWith(EnvelopsComparator()) //先將信封排序

    val height = IntArray(n)//將二維問題降唯一維
    for(i in 0 until n){
        height[i] = envelops[i][1]
    }
    return lengthOfLIS(height.toTypedArray())//使用一般的LIS得到答案
}

class EnvelopsComparator : Comparator<IntArray> {
    override fun compare(a: IntArray?, b: IntArray?): Int {
        if (a!![0] == b!![0]) { //如果w相同 就根據h降冪排序
            return when {
                a[1] > b[1] -> {
                    -1
                }
                a[1] < b[1] -> {
                    1
                }
                else -> {
                    0
                }
            }
        } else {
            return when {//如果w不同 就根據w升冪排序
                a[0] > b[0] -> {
                    1
                }
                a[0] < b[0] -> {
                    -1
                }
                else -> {
                    0
                }
            }
        }
    }
}

這題還能更加進階一點，如果不是信封而是三維的箱子呢?要怎麼解呢？
遵循剛剛的想法，我們先排長寬高的其中一邊，再從剩下的挑一邊出來...最後做LIS...可以嗎？
答案是...不行!!變成三維後，題目的難度陡然上升，要使用到一種樹狀陣列...這個我們之後再講吧！